
class Node:

    __slots__ = "son", 'end'
    def __init__(self):
        self.son = {}
        self.end =False


# 前缀树

class Trie:

    def __init__(self):
        
        self.root = Node()
        # pass

    def insert(self, word):
        # pass
        cur = self.root
        for c in word:
            if c not in cur.son:
                cur.son[c] = Node()
            
            cur = cur.son[c]
        cur.end = True

    
    def find(self, word: str) -> int:
        cur = self.root
        for c in word:
            if c not in cur.son:  # 道不同，不相为谋
                return 0
            cur = cur.son[c]
        # 走过同样的路（2=完全匹配，1=前缀匹配）
        return 2 if cur.end else 1

    def search(self, word):
        # pass
        return self.find(word) == 2
        
    

    def startsWith(self, prefix):
        return self.find(prefix) != 0
